home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / listings / v_09_07 / 9n07018a < prev    next >
Encoding:
Text File  |  1991-05-21  |  8.5 KB  |  328 lines
  1.  
  2. /* --------------------------------------------------------------
  3.  
  4. This program allocates memory for an array ary, as follows:
  5.  
  6.     struct node ary[MAX_NODES];
  7.  
  8. Each element of this array represents a link in a linked list.  The
  9. user can perform various operations on the whole list or on specific
  10. nodes within it.  They may, for example, add, remove, or change a
  11. node, or display or sort the whole list.
  12.  
  13.  
  14.  
  15. -------------------------------------------------------------- */
  16.  
  17. #include <stdio.h>
  18. #include <ctype.h>
  19.  
  20. #define MAX_NODES 4    /* max number of nodes in array */
  21. #define EOLIST (-1)    /* end-of-list indicator for fwd_ptr */
  22.  
  23. #define ADD_NODE 'A'
  24. #define CHANGE_NODE 'C'
  25. #define DISPLAY_NODE 'D'
  26. #define EXIT 'E'
  27. #define SEARCH_FNODE 'F'
  28. #define HELP '?'
  29. #define INSERT_NODE 'I'
  30. #define COUNT_NODES 'N'
  31. #define REMOVE_NODE 'R'
  32. #define SORT_NODES 'S'
  33. #define DUMP_LIST 'T'
  34.  
  35. void init_free_list(void);
  36. int get_free_node(void);
  37. void put_free_node(int node);
  38.  
  39. struct node {
  40.     int value;    /* the node's data value */
  41.     int fwd_ptr;    /* ptr to next node in list */
  42. };
  43.  
  44. struct node ary[MAX_NODES];
  45. int root_node = EOLIST;    /* start of list */
  46. int tail_node = EOLIST;    /* end of list */
  47. int free_node = 0;    /* next free node */
  48. int nodes_in_use = 0;
  49.  
  50. /* ----------------------------------------------------------- */
  51.  
  52. main()
  53. {
  54.     int node, new_node;
  55.     int temp, i, j, k;
  56.     int inchar = 'x';    /* force initial prompt */
  57.     int done = 0;
  58.  
  59. /* ----------------------------------------------------------- */
  60.  
  61.     init_free_list();
  62.  
  63.     while (!done) {
  64.         if (inchar != ' ')
  65.             printf("\nEnter Action Code (%c for help): ", HELP);
  66.         switch(toupper(inchar = getchar())) {
  67.  
  68. /* ----------------------------------------------------------- */
  69.  
  70.     case EXIT:
  71.         done = 1;
  72.         break;
  73.  
  74. /* ----------------------------------------------------------- */
  75.  
  76.     default:
  77.         printf("\n   Invalid command. Please try again\n");
  78.         break;
  79.  
  80. /* ----------------------------------------------------------- */
  81.  
  82.     case HELP:
  83.         printf("\n   The action codes are:\n");
  84.         printf("\t%c - produces this help message\n", HELP);
  85.         printf("\t%c - Add a new node to the end\n", ADD_NODE);
  86.         printf("\t%c - Change a user-selected node\n", CHANGE_NODE);
  87.         printf("\t%c - Display a user-selected node\n", DISPLAY_NODE);
  88.         printf("\t%c - Exit this program\n", EXIT);
  89.         printf("\t%c - Search for first occurrence\n", SEARCH_FNODE);
  90.         printf("\t%c - Insert a new node\n", INSERT_NODE);
  91.         printf("\t%c - Report the number of nodes\n", COUNT_NODES);
  92.         printf("\t%c - Remove a user-selected node\n", REMOVE_NODE);
  93.         printf("\t%c - Sort the nodes in ascending order\n", SORT_NODES);
  94.         printf("\t%c - Show all entries in the list\n", DUMP_LIST);
  95.         break;
  96.  
  97. /* ----------------------------------------------------------- */
  98.  
  99.     case '\n':    /* ignore white space on input */
  100.     case ' ' :
  101.     case '\t':
  102.     case '\v':
  103.     case '\f':
  104.         inchar = ' ';    /* indicate white space input */
  105.         break;
  106.  
  107. /* --------------------------------------------------------------
  108.  
  109. ADD_NODE: The steps to add a new node to the end of the list are:
  110.  
  111. A.  Get a new free node from free node list.  If no more, get out.
  112.  
  113. B.  Have a new node so fill it with data.
  114.  
  115. C.  If this is the first node, make it the root otherwise update the
  116.     forward pointer from the previous end-of-list node to point to
  117.     this new end-of-list node.
  118.  
  119. D.  Indicate this is the new end-of-list node and update tail node.
  120.  
  121. -------------------------------------------------------------- */
  122.  
  123.     case ADD_NODE:
  124.  
  125. /*A*/        if ((new_node = get_free_node()) == EOLIST) {
  126.             printf("\n   List is full\n");
  127.             break;
  128.         }
  129.  
  130. /*B*/        printf("\n   Enter new node's value: ");
  131.         scanf("%3d", &ary[new_node].value);
  132.  
  133. /*C*/        if (root_node == EOLIST)
  134.             root_node = new_node;
  135.         else
  136.             ary[tail_node].fwd_ptr = new_node;
  137.  
  138. /*D*/        ary[new_node].fwd_ptr = EOLIST;
  139.         tail_node = new_node;
  140.         printf("\n   Node added");
  141.         break;
  142.  
  143. /* --------------------------------------------------------------
  144.  
  145. DUMP_LIST: The steps to display all nodes in the list are:
  146.  
  147. A.  Complain if list empty.
  148.  
  149. B.  Traverse list starting at the root node displaying each node's 
  150.     data and forward pointer.
  151.  
  152. -------------------------------------------------------------- */
  153.  
  154.     case DUMP_LIST:
  155.  
  156. /*A*/        if (root_node == EOLIST) {
  157.             printf("\n   List contains no nodes\n");
  158.             break;
  159.         }
  160.  
  161.         printf("\n   List nodes are as follows:\n");
  162. /*B*/        node = root_node;
  163.         while (node != EOLIST) {
  164.             printf("\t[%d] => %3d, fwd_ptr: %3d\n", node, 
  165.                 ary[node].value, ary[node].fwd_ptr);
  166.             node = ary[node].fwd_ptr;
  167.         }
  168.  
  169.         break;
  170.  
  171. /* --------------------------------------------------------------
  172.  
  173. COUNT_NODES: Just display the counter we've been keeping.
  174.  
  175. -------------------------------------------------------------- */
  176.  
  177.     case COUNT_NODES:
  178.         printf("\tThere are %d nodes in the list\n", nodes_in_use);
  179.         break;
  180.  
  181. /* --------------------------------------------------------------
  182.  
  183. DISPLAY_NODE: The steps to display a selected node are:
  184.  
  185. A.  Complain if list empty.
  186.  
  187. B.  Get the node number from the user. Note that the first node in the 
  188.     list is number 0, then 1, 2, etc. The number of the node and the 
  189.     subscript it occupies in ary are NOT related even though they can 
  190.     be the same.
  191.  
  192. C.  Traverse list starting at the root node looking for the requested 
  193.     node. When it is found, display its data and forward pointer.
  194.  
  195. -------------------------------------------------------------- */
  196.  
  197.     case DISPLAY_NODE:
  198.  
  199. /*A*/        if (root_node == EOLIST) {
  200.             printf("\n   List contains no nodes\n");
  201.             break;
  202.         }
  203.  
  204. /*B*/        while (1) {
  205.             printf("\n   Enter node number: ");
  206.             scanf("%d", &node);
  207.             if (node >= 0 && node < nodes_in_use)
  208.                 break;
  209.  
  210.             printf("\n   No such node (%d) in list\n", node);
  211.         }
  212.  
  213. /*C*/        j = root_node;        /* find nth node */
  214.         for (i = 0; i < node; ++i)
  215.             j = ary[j].fwd_ptr;
  216.  
  217.         printf("\t[%d] => %3d, fwd_ptr: %3d\n", j, 
  218.             ary[j].value, ary[j].fwd_ptr);
  219.         break;
  220.  
  221. /* --------------------------------------------------------------
  222. The rest of the cases will be published next month.
  223. -------------------------------------------------------------- */
  224.  
  225.         }
  226.     }
  227.  
  228.     return (0);
  229. }
  230. /* ----------------------------------------------------------- */
  231.  
  232. /* --------------------------------------------------------------
  233.  
  234. FUNCTION init_free_list
  235.  
  236. Initialize the list of free nodes using the following steps:
  237.  
  238. A.  Initialize various counters and pointers.
  239.  
  240. B.  Since all nodes are in the free list, have each node point to the
  241.     array element immediately following.
  242.  
  243. C.  The last node has a special forward pointer to indicate the
  244.     it is the end-of-list.
  245.  
  246. -------------------------------------------------------------- */
  247.  
  248. void init_free_list(void)
  249. {
  250.     int i;
  251.  
  252. /*A*/    free_node = 0;    /* [0] is first free node */
  253.     nodes_in_use = 0;
  254.     root_node = EOLIST;
  255.     tail_node = EOLIST;
  256.  
  257. /*B*/    for (i = 0; i < MAX_NODES; ++i)
  258.         ary[i].fwd_ptr = i + 1;
  259.  
  260. /*C*/    ary[MAX_NODES - 1].fwd_ptr = EOLIST;
  261. }
  262.  
  263. /* --------------------------------------------------------------
  264.  
  265. FUNCTION get_free_node
  266.  
  267. Get a node from the free node list using the following steps:
  268.  
  269. A.  Since free_node always points to the first node in the free list, 
  270.     always return that value. If the free list is empty, free_node 
  271.     will be EOLIST and that's what we want to return in such a 
  272.     condition anyway.
  273.  
  274. B.  If there is actually a free node, make free_node point to the next 
  275.     free node in the list and increment allocated node count. If there 
  276.     are no more nodes in the free list, free_note will conveniently be 
  277.     set to EOLIST.
  278.  
  279. C.  Return the subscript of the next available free node or EOLIST.
  280.  
  281. -------------------------------------------------------------- */
  282.  
  283. int get_free_node(void)
  284. {
  285. /*A*/    int new_node = free_node;
  286.  
  287. /*B*/    if (free_node != EOLIST) {
  288.         free_node = ary[free_node].fwd_ptr;
  289.         ++nodes_in_use;
  290.     }
  291.  
  292. /*C*/    return new_node;
  293. }
  294.  
  295. Output:
  296.  
  297. Enter Action Code (? for help): a
  298.  
  299.    Enter new node's value: 100
  300.  
  301.    Node added
  302. Enter Action Code (? for help): a
  303.  
  304.    Enter new node's value: 200
  305.  
  306.    Node added
  307. Enter Action Code (? for help): a
  308.  
  309.    Enter new node's value: 500
  310.  
  311.    Node added
  312. Enter Action Code (? for help): t
  313.  
  314.    List nodes are as follows:
  315.     [0] => 100, fwd_ptr:   1
  316.     [1] => 200, fwd_ptr:   2
  317.     [2] => 500, fwd_ptr:  -1
  318.  
  319. Enter Action Code (? for help): n
  320.  
  321.     There are 3 nodes in the list
  322.  
  323. Enter Action Code (? for help): d
  324.  
  325.    Enter node number: 0
  326.        [0] => 100, fwd_ptr:   1
  327.  
  328.